#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class Solution01 {
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    queue<pair<int, int>> q;
    bool vis[51][51] = { 0 };
    int m, n;
    int newColor;
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        m = image.size(), n = image[0].size();
        newColor = color;
        int targetColor = image[sr][sc];
        // if (image[sr][sc] == 0) return image;
        image[sr][sc] = newColor, vis[sr][sc] = true;
        // 从source位置开始入队列
        q.push({sr, sc});
        while (!q.empty()) {
            auto x = q.front().first;
            auto y = q.front().second;
            q.pop();
            image[x][y] = newColor, vis[x][y] = true;
            for (int k = 0; k < 4; k++) {
                int i = x + dx[k], j = y + dy[k];
                if (i >= 0 && j >= 0 && i < m && j < n && !vis[i][j] && image[i][j] == targetColor)
                    q.push({i, j});
            }
        }
        return image;
    }
};

class Solution02 {
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    // bool vis[310][310] = { 0 };
    vector<vector<bool>> vis;
    using PII = pair<int, int>;
    int m, n;
public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        int retcnt = 0;
        vis.resize(m, vector<bool>(n, false));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !vis[i][j]) {
                    retcnt++;
                    bfs(grid, i, j);
                }
            }
        }

        return retcnt;
    }

    void bfs(vector<vector<char>>& grid, int i, int j) {
        // vis[i][j] = true;
        queue<PII> q;
        q.push({i, j});
        vis[i][j] = true;
        while (!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop();
            for (int k = 0; k < 4; k++) {
                int a = dx[k]  + x, b = dy[k] + y;
                if (a >= 0 && b >= 0 && a < m && b < n && grid[a][b] == '1' && !vis[a][b]) {
                    q.push({a, b});
                    vis[a][b] = true;
                }
            }
        }
    }
};

class Solution03 {
    int m, n;
    vector<vector<bool>> vis;
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };

    using PII = pair<int, int>;
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        vis.resize(m, vector<bool>(n, false));
        int ret = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] && !vis[i][j])  {
                    int num = bfs(grid, i, j);
                    ret = max(ret, num);
                }
            }
        return ret;
    }

    int bfs(vector<vector<int>>& grid, int i, int j) {
        vis[i][j] = true;
        queue<PII> q;
        q.push({i, j});

        int num = 0;
        while (!q.empty()) {
            num++;
            PII f = q.front();
            q.pop();
            int a = f.first, b = f.second;
            for (int k = 0; k < 4; k++) {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y] && !vis[x][y]) {
                    vis[x][y] = true;
                    q.push({x, y});
                }
            }
        }
        return num;
    }
};

class Solution04 {
    int m, n;
    vector<vector<bool>> vis;
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };   
    using PII = pair<int, int>;

public:
    void solve(vector<vector<char>>& board) {
        m = board.size(), n = board[0].size();
        vis.resize(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') bfs(board, i, 0);
            if (board[i][n - 1] == 'O') bfs(board, i, n - 1);
        }

        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') bfs(board, 0, j);
            if (board[m - 1][j] == 'O') bfs(board, m - 1, j);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '.') board[i][j] = 'O';
                else if (board[i][j] == 'O') board[i][j] = 'X';
                cout << board[i][j] << " ";
            }
            cout << endl;
        }

    }

    void bfs(vector<vector<char>>& board, int i, int j) {
        queue<PII> q;
        q.push({i, j});
        board[i][j] = '.';

        while (!q.empty()) {
            PII front = q.front();
            q.pop();
            int a = front.first, b = front.second;
            for (int k = 0; k < 4; k++) {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && y >= 0 && x < m && y < n && board[x][y] == 'O') {
                    board[x][y] = '.';
                    q.push({x, y});
                }
            }
        }
    }
};

class Solution05 {
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    using PII = pair<int, int>;
    bool vis[101][101] = {0};
    int m, n;

public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        m = maze.size(), n = maze[0].size();
        memset(vis, 0, sizeof(vis));
        queue<PII> q;
        int ex = entrance[0], ey = entrance[1];
        vis[ex][ey] = true;
        if (ex >= m && ey >= n) return -1;
        q.push({entrance[0], entrance[1]});

        int cnt = 0;


        while (!q.empty()) {
            int sz = q.size();
            cnt++;

            for (int i = 0; i < sz; i++) {
                PII front = q.front();
                int a = front.first, b = front.second;
                q.pop();
                for (int k = 0; k < 4; k++) {
                    int x = a + dx[k], y = b + dy[k];
                    if (x >= 0 && y >= 0 && x < m && y < n && maze[x][y] == '.' && !vis[x][y]) {
                        // 将x y放入队列中
                        vis[x][y] = true;
                        q.push({x, y});
                        if (isEdge(x, y))
                            return cnt;
                    }
                }
            }
        }
        return -1;
    }

    bool isEdge(int x, int y) { return x == m - 1 || y == n - 1 || x == 0 || y == 0; }
};

class Solution06 {
public:
    // int minMutation(string startGene, string endGene, vector<string>& bank) {
    //     bool flag = true;
    //     for (auto& e : bank) if (e == endGene) flag = false;

    //     if (flag) return -1;

    //     int num = 0;
    //     for (int i = 0; i < 8; i++) {
    //         if (startGene[i] != endGene[i]) num++;
    //     }
    //     if (num > bank.size()) return -1;

    //     unordered_map<string, int> hash;
    //     for (auto& s : bank) hash[s] = false;
    //     queue<string> q;
    //     q.push(startGene);
        
    //     int cnt = 0;

    //     while (!q.empty()) {
    //         cnt++;
    //         int sz = q.size();
    //         // 会产生n中变化，模拟这n中变换，在hash表中则加入到队列中
    //         for (int i = 0; i < sz; i++) {
    //             string str = q.front();
    //             q.pop();
    //             if (str == endGene) return cnt - 1;
    //             bool x = EnterQueue(q, hash, str, endGene, bank);
    //             if (x == false) break;
    //         }
    //     }

    //     return -1;
    // }

    bool EnterQueue(queue<string>& q, unordered_map<string, int>& hash, string& str, string& endGene, vector<string>& bank) {
        // 开始根据串进行变化
        int len = str.size();
        // for (int i = 0; i < len; i++) {
        //     if (str[i] != endGene[i]) {
        //         string tmp(str);
        //         tmp[i] = endGene[i];
        //         if (hash.count(tmp)) q.push(tmp);
        //     }
        // }
        int flag = false;
        for (auto& e : bank) {
            int cnt = 0;
            for (int i = 0; i < len; i++) {
                if (e[i] != str[i]) cnt++;
            }
            if (cnt == 1) q.push(e), flag = true;
        }
        return flag;
    }


    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> vis, hash(bank.begin(), bank.end());
        if (!hash.count(endGene)) return -1;
        queue<string> q;
        q.push(startGene);
        vis.insert(startGene);

        string change("ACGT");
        int ret = 0;

        while (!q.empty()) {
            ret++;
            int sz = q.size();
            
            while (sz--) {
                string t = q.front();
                q.pop();
                for (int i = 0; i < 8; i++) {
                    string tmp(t);
                    for (int j = 0; j < 4; j++) {
                        tmp[i] = change[j];
                        if (hash.count(tmp) && !vis.count(tmp)) {
                            if (tmp == endGene) return ret;
                            vis.insert(tmp);
                            q.push(tmp);
                        }
                    }
                }
            }
        }

        return -1;
    }
};

int main() {

    return 0;
}